//
// Created by Administrator on 2021/9/9.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    int repeatedNTimes(vector<int> &nums) {
        unordered_set<int> s;
        for (int &x: nums) {
            if (s.count(x))
                return x;
            s.insert(x);
        }
        return -1;
    }

    int repeatedNTimes2(vector<int> &nums) {
        // 占据一半的数字 其分布必然是相互间隔 或者有相邻的
        for (int i = 0; i < nums.size() - 1; i += 2) {
            if (nums[i] == nums[i + 1])
                return nums[i];
        }
        // 没有相邻的，就必然是均匀分布 在前4个中有2个
        unordered_set<int> s;
        for (int i = 0; i <= 3; ++i) {
            if (s.count(nums[i]))
                return nums[i];
            s.insert(nums[i]);
        }
        return -1;
    }

    int repeatedNTimes3(vector<int> &nums) {
        for (int k = 1; k <= 3; ++k)
            for (int i = 0; i < nums.size() - k; ++i)
                if (nums[i] == nums[i + k])
                    return nums[i];
        return -1;
    }


};

int main() {
    vector<int> nums{1, 2, 3, 3};
    Solution solution;
    cout << solution.repeatedNTimes3(nums) << endl;
    return 0;
}
